package 中等.模拟;

/**
 * 给你一个下标从 0 开始的字符串 expression ，格式为 "<num1>+<num2>" ，其中 <num1> 和 <num2>
 * 表示正整数。
 * 请你向 expression 中添加一对括号，使得在添加之后， expression 仍然是一个有效的数学表达式，
 * 并且计算后可以得到 最小 可能值。左括号 必须 添加在 '+' 的左侧，而右括号必须添加在 '+' 的右侧。
 * 返回添加一对括号后形成的表达式 expression ，且满足 expression 计算得到 最小 可能值。如果存在
 * 多个答案都能产生相同结果，返回任意一个答案。
 * 生成的输入满足：expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合
 * 32-bit 带符号整数范围。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimize-result-by-adding-parentheses-to-expression
 */
public class 向表达式添加括号后的最小结果_6038 {

    public static void main(String[] args) {

        System.out.println(minimizeResult("999+999"));

    }

    /**
     * 直接模拟枚举所有情况，找出最小的
     * 定义：a1*(a2+b1)*b2
     *
     * @param expression
     * @return
     */
    public static String minimizeResult(String expression) {
        String[] split = expression.split("\\+");
        StringBuilder stringBuilder = null;
        int minSum = Integer.MAX_VALUE;
        // 定义左括号在index的左边
        for (int i = 0; i < split[0].length(); i++) {
            // 注意边界问题
            String a1Str = i == 0 ? "" : split[0].substring(0, i), a2Str = split[0].substring(i);
            int a1 = i == 0 ? 1 : Integer.valueOf(a1Str);
            int a2 = Integer.valueOf(a2Str);
            // 定义右括号在index的右边
            for (int j = 0; j < split[1].length(); j++) {
                String b1Str = split[1].substring(0, j + 1), b2Str = j == split[1].length() - 1 ? "" : split[1].substring(j + 1);
                int b1 = Integer.valueOf(b1Str);
                int b2 = j == split[1].length() - 1 ? 1 : Integer.valueOf(b2Str);
                if (a1 * (a2 + b1) * b2 < minSum) {
                    // 更新最小值
                    minSum = a1 * (a2 + b1) * b2;
                    stringBuilder = new StringBuilder();
                    stringBuilder.append(a1Str).append("(").append(a2Str)
                            .append("+").append(b1Str).append(")")
                            .append(b2Str);
                }
            }
        }
        return stringBuilder.toString();
    }

}
